package org.hw.algorithm.string;

import org.hw.algorithm.common.CommonUtils;

import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

/**
 * @program: algorithm
 * @description:
 * @author: hewei
 * @date: 2023-05-29 11:03
 **/

public class StringFactory {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

//        String str="abcdabcd";
//        String str1="abcdcba";
//        System.out.println(longestPalindrome(str));
//        System.out.println(isPalindrome(str));
//        System.out.println(longestCommonPrefix(new String[]{str, str1}));


        sc.close();
//        System.out.println(depthBrackets(s));
        System.out.println(strToInt(s));
    }


    /*求可构造的最长回文串长度*/
    public static int longestPalindrome(String s) {
        if (s.isEmpty()) return 0;
        char[] chars = s.toCharArray();
        HashSet<Character> charsSet = new HashSet<>();
        int longest = 0;

        for (char c : chars) {
            if (charsSet.contains(c)) {
                charsSet.remove(c);
                longest += 1;
            } else {
                charsSet.add(c);
            }
        }

        return charsSet.size() == 0 ? longest * 2 : longest * 2 + 1;
    }

    /*是否回文串*/
    public static boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) == s.charAt(r)) {
                l++;
                r--;
            } else {
                return false;
            }
        }
        return true;
    }

    /* 合法的括号序列的深度,例如只包含小括号的序列："((()))" 深度为3 */
    public static int depthBrackets(String s) {
        int cnt = 0, max = 0, i;
        for (i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(')
                cnt++;
            else
                cnt--;
            max = Math.max(max, cnt);
        }
        return max;
    }

    /**
     * <h>最长公共子串</h>
     * -------------------------------------------------------------------------------------------------------------------
     * 子串：是在父串中连续的字符串。在二维数组中，连续的子串在二维数组中由左上方至右下方连续分布
     * 该代码使用了动态规划的思想，定义了一个二维数组arr，其中arr[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子串的长度。
     * 如果str1的第i个字符和str2的第j个字符相等，则arr[i][j]等于arr[i-1][j-1]+1，否则arr[i][j]等于0。
     * 在遍历arr数组的过程中，记录最长长度和对应的结束位置，最后从str1中截取该位置的前maxLength个字符即为最长公共子串。
     * */

    /**
     * 最长公共子串二（精简写法）:
     * 创建数组行列分别增加一格，方便计算
     * arr[i][j] 的值表示左上角位置arr[i-1][j-1]字符串相等的最长长度
     */
    public static String longestComSubStr(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] arr = new int[len1 + 1][len2 + 1];
        int maxLength = 0;
        int endIndex = 0;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                    if (maxLength < arr[i][j]) {
                        maxLength = arr[i][j];
                        endIndex = i;
                    }
                }
            }
        }
        /*[start,end) 字符串截取到start-end，调用substring(start,end+1)取出的字符串才是start-end的范围 */
        return str1.substring(endIndex - maxLength, endIndex);
    }

    /**
     * <h>最长公共子序列</h>
     * -------------------------------------------------------------------------------------------------------------------
     *  子序列：字符在都在父串中，字符可以不连续，但是需要和父串顺序相同。子序列中的字符在二维数组中的分布是离散的。
     *  子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 该代码同样使用了动态规划的思想，定义了一个二维数组arr，其中arr[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。
     * 如果str1的第i个字符和str2的第j个字符相等，则arr[i][j]等于arr[i-1][j-1]+1，否则arr[i][j]等于arr[i-1][j]和arr[i][j-1]中的较大值。
     * 最后返回arr[len1][len2]即为最长公共子序列的长度
     * */

    /**
     * 最长公共子序列长度
     */
    public static int longestComSubSequenceLength(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] arr = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
                }
            }
        }
        /*数组的最右下方的元素值即为最长子序列长度*/
        return arr[len1][len2];
    }

    // 最长公共子序列
    public static String longestComSubSequence(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] arr = new int[len1 + 1][len2 + 1];
        StringBuilder lcs = new StringBuilder();

        // 填充arr数组
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
                }
            }
        }

        // 从右下角开始回溯
        int i = len1, j = len2;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (arr[i - 1][j] > arr[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // 由于我们从右下角开始回溯，得到的子序列是逆序的，所以需要反转
        return lcs.reverse().toString();
    }

    /**
     * 最长公共前缀
     * 1、以第一个字符串为基准，匹配其他字符串中的每一位字符
     * 2、匹配终止条件：“与基准字符串当前字符不相等或者目标串的长度小于基准串时”
     * 3.如果匹配结束也没有满足 终止条件，则返回基准字符串
     * */
    public static String longestCommonPrefix(String[] strs) {
        String base = strs[0];
        for (int i = 0; i < base.length(); i++) {
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].length() <= i || base.charAt(i) != strs[j].charAt(i)) {
                    return base.substring(0,i);
                }
            }
        }
        return base;
    }

    /**
     * 判断一个字符串是否包含重复字符
     * 共有256（2^8）个字符，用8个int（一个int占4字节共32位）共256位表示
     * 原理类似 HashMap，8个容量的bits数组相当于8个桶，每个桶是一个int类型（4个字节，共32位）。
     * (int)char / 32 ：表示 char 在那个桶里；(int)char % 32 ：表示 char 在桶中哪个位置。
     * 用每一位来标记是否存在，1存在，0不存在
     */
    public static boolean doubleStr(String str) {
        int[] bits = new int[8];
        int len = str.length();
        for (int i = 0; i < len; i++) {
            /*取数组下标*/
            int index = (int) str.charAt(i) / 32;
            /*取数组中的位移*/
            int offset = (int) str.charAt(i) % 32;
            /*判断字符所在位置是否已存在*/
            if (((bits[index]) & (1 << offset)) != 0) {
                return true;
            }
            /*遍历过的元素位置设为1*/
            bits[index] |= (1 << offset);
        }
        return false;
    }

    /**
     * 求一个字符串的全排列（精简写法）
     * chars 目标字符串数组，start 起始字符下标，end 结束字符下标
     * 利用回溯算法输出每一种可能
     */
    public static void permutations(char[] chars, int start, int end) {
        if (chars == null || chars.length == 0) return;
        if (start == end) System.out.println(chars);
        for (int i = start; i <= end; i++) {
            /*交换start与i的位置*/
            CommonUtils.swap(chars, start, i);
            /*固定第一个字符，对剩余的进行全排列*/
            permutations(chars, start + 1,end);
            /*还原start与i的位置*/
            CommonUtils.swap(chars, start, i);
        }
    }
    /**
     * 求一个字符串的全排列（回溯算法经典写法）
     * choices 所有的选项（原始字符数组）；state 当前的排列结果；result 整个方法的结果集
     * 基本形式：
     * 一、结束条件，记录结果
     * 二、迭代所有选项
     * 1. 剪枝
     * 2. 当前结果添加选项
     * 3. 递归所有选项
     * 4. 回溯
     * */
    public static void permutations(char[] choices, List<Character> state, List<String> result) {
        // 结束条件
        if (state.size() == choices.length) {
            // 将满足条件的当前结果添加到结果集
            result.add(state.toString());
            return ;
        }
        // 回溯中的迭代
        for (int i = 0; i < choices.length ; i++) {
            // 剪枝操作
            if (state.contains(choices[i])) continue;
            // 向当前结果中添加可能的选项
            state.add(choices[i]);
            // 递归所有选项
            permutations(choices,state,result);
            // 回溯，恢复当前结果集
            state.remove((Character) choices[i]);
        }
    }

    /**
     * "123" : 1x10+2 -> 12x10+3
     * 字符串转换成整数
     */
    public static int strToInt(String s) {
        if (s.isEmpty()) return 0;
        int result = 0;
        int flag = s.startsWith("-") ? -1 : 1;
        int start = s.startsWith("-") || s.startsWith("+") ? 1 : 0;
        for (int i = start; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                result = result * 10 + (s.charAt(i) - '0');
            } else {
                return 0;
            }
        }
        return result*flag;
    }

    /**
     * 字符串匹配
     * text 目标串 ；pattern 模式串
     * 1.迭代目标串，迭代终止条件为 [text长度]-[pattern长度](m-n)，因为 text串结尾剩余 pattern的长度个子串时只需要第一位匹配一次就可以了，再往后的子串长度小于pattern。
     * 2.目标串和模式串对应每一位进行比较，不相等就跳出循环
     * 3.模式串所有字符迭代完成，说明匹配成功
     */
    public static int strMatch(String text, String pattern) {
        if ("".equals(text) || "".equals(pattern)) return -1;
        int m=text.length();
        int n=pattern.length();
        for (int i = 0; i <= m-n; i++) {
            int j;
            for (j = 0; j < n; j++) {
                if (text.charAt(i+j)!=pattern.charAt(j)) break;
            }
            if (j==n) return i;
        }
        return -1;
    }

    /**************************************************回文字符串**********************************************/

    /**
     * 求字符串的最长回文子串
     * */
    public static String longestPalindrom(String s) {
        if (null==s || s.isEmpty()) return "";
        //最长回文子串的起始和结束索引
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            //以单个字符为中心扩展（偶数个字符的子串）
            int len1 = expandCenter(s, i, i);
            //以两个相邻字符为中心扩展（奇数个字符的子串）
            int len2=expandCenter(s,i,i+1);
            // 取较长的回文长度
            int len = Math.max(len1, len2);
            // 更新开始和结束索引
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end+1);
    }
    /**
     * 中心扩展法求回文长度
     */
    public static int expandCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    /**************************************************回文字符串**********************************************/

/**************************************************KMP算法**********************************************/
    /**
     * 字符串：ABCDAB
     * 前缀：[A,AB,ABC,ABCD,ABCDA]
     * 后缀：[BCDAB,CDAB,DAB,AB,B]
     * 部分匹配表：[AB]
     * 移动位数：已匹配的字符数 - 对应的部分匹配表的字符数
     * 部分匹配表就是前缀和后缀的公共部分，匹配值：A，B（[1,2]）
     * <p>
     * 1.求出部分匹配表
     * 2.字符串匹配
     * 3.求匹配下标
     */
    public static int strMatchKMP(String str1, String str2, int[] next) {
        if (str1 == null || str2 == null) {
            return -1;
        }
        int len = str1.length();
        for (int i = 0, j = 0; i < len; i++) {
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) return i - j + 1;
        }
        return -1;
    }

    /*部分匹配表计算*/
    public static int[] kmpNext(String str) {
        int len = str.length();
        int[] next = new int[len];
        next[0]=0;
        for (int i = 1, j = 0; i < len; i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
/**************************************************KMP算法**********************************************/
}
